package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

// 题目: https://www.nowcoder.com/interview/ai/446068
// 在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径，返回 1 到 n 的最短路径值。如果 1 无法到 n ，输出 -1, 图中可能有重边，无自环
// 平台上测试已经通过
public class FindShortestPath_NowCoder {
    static class Node implements Comparable<Node> {
        // 节点下标
        int index;

        // 当前k到该节点的距离
        int dist;

        public Node(int index, int dist) {
            this.index = index;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node that) {
            return this.dist - that.dist;
        }
    }

    static class Edge {
        int toIndex;
        int weight;

        public Edge(int toIndex, int weight) {
            this.toIndex = toIndex;
            this.weight = weight;
        }
    }

    // m没啥用
    public int findShortestPath(int n, int m, int[][] edges) {
        final int start = 1;
        final int target = n;
        // 注意原二维数组不是邻接表, 下标从1开始
        List<Edge>[] g = buildWeightedGraph(edges, n);

        // 当前k到各个节点的距离, 用于q中去除过时的节点
        int[] minDist = new int[n+1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[start] = 0;

        // q相当于原算法中的V-S去除了minDist=INF的那部分, 没有显示的S.
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(start, 0));

        // 内部加外部循环叠加总共会遍历|E|次, 堆操作是O(log|V|), 所以复杂度是O(ElogV)
        // 但是q的节点数最大可能是O(log|E|), 因此实际的复杂度是O(ElogE)
        while (!q.isEmpty()) {
            Node curr = q.poll();
            if (minDist[curr.index] < curr.dist) {
                // 已经有更短的路径在curr入队后出现了, curr是过时的, 应该忽略
                // 相当于 visited[curr.index] = true, 直接返回
                continue;
            }

            // 如果只求k到固定节点t的路径, 就只需要加一个判断就可以了
            if (curr.index == target) {
                return curr.dist;
            }

            // 否则, 需要设置 visited[curr.index] = true;

            // 更新curr的临接节点, 如果找到更短的路径, 就放入q中
            // for循环执行n次
            for (Edge edge: g[curr.index]) {
                int newDist = minDist[curr.index] + edge.weight;
                if (newDist < minDist[edge.toIndex]) {
                    // 相当于 visited[j] = false, 需要放入q中
                    minDist[edge.toIndex] = newDist;
                    // 由于minDist[j]已被更新, 后续最新的Node(j)会"覆盖"老的Node(j)
                    q.offer(new Node(edge.toIndex, minDist[edge.toIndex]));
                }
            }
        }
        // minDist中至少一个为INF, 就是不可达
        // 或者visited中至少有一个为false, 就是不可达
        int max = 0;
        for (int i = 1; i <= n; i++) {
            if (minDist[i] == Integer.MAX_VALUE) {
                System.out.format("n: %d, k: %d, max: %d\n", n, start, -1);
                return -1;
            }
            max = Math.max(max, minDist[i]);
        }
        System.out.format("n: %d, k: %d, max: %d\n", n, start, max);
        return max;
    }

    public List<Edge>[] buildWeightedGraph(int[][] edges, int n) {
        // 泛型数组: 由于类型擦除，在运行时无法知道确切的类型信息，因此不能new相应类型的数组。但可以声明.
        List<Edge>[] graph = new List[n+1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>(n);
        }
        for (int[] edge: edges) {
            int fromIndex = edge[0];
            int toIndex = edge[1];
            int weight = edge[2];
            graph[fromIndex].add(new Edge(toIndex, weight));
        }
        return graph;
    }
}
